package base.day07;

/**
 * 描述：
 *      求岛屿的数量
 *      拓展：当岛屿面积特别大时，设计一种框架进行快速计算？
 *      我们可以采用分治的思想，将一块大的面积，进行切分，切分成多块小的面积，然后利用多核并行处理。
 *      分别计算出每块面积的岛屿数量，然后进行合并。
 *      合并的时候，只需要收集边界信息，然后用并查集的思想，判断边界合并的条件，快速合并。
 * @author hl
 * @version 1.0
 * @date 2020/10/29 11:03
 */
public class Code_01_Islands {
    public static int countIslands(int[][] matrix){
        int num = 0;
        int M = matrix.length;
        int N = matrix[0].length;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1) {
                    infect(matrix, i, j);
                    num++;
                }
            }
        }
        return num;
    }
    private static void infect(int[][] matrix, int i, int j) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[i].length || matrix[i][j] != 1) {
            return ;
        }
        matrix[i][j] = 2;
        infect(matrix,i - 1, j);
        infect(matrix, i, j + 1);
        infect(matrix,i + 1, j);
        infect(matrix, i,j - 1);
    }
    public static void main(String[] args) {
        int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 0, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m1));

        int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 1, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m2));

    }
}
